#include "grafo.h"
#include "common.h"
#include <iostream>
using namespace std;
/*======================================================================
	Algoritmo de busqueda local
------------------------------------------------------------------------

======================================================================*/

//Devuelve si la componente pasada del grafo esta dominada por
//los nodos del conjunto.
static bool dominaComponente(
	const Grafo & grafo, 
	const vint & componente, 
	const vint & conjunto,
	int aIgnorar = -1
){
	
	bool es = true;
	int	nodosComponente = componente.size(),
		nodosConjunto = conjunto.size();
		
	vint dominado(grafo.nodos(),0);
	for(int i = 0; i < nodosConjunto; i++){
		int nodo = conjunto[i];
		
		if(nodo == aIgnorar) continue;

		const vint & vecino = grafo.vecinos(nodo);
		int vecinos = vecino.size();

		dominado[nodo]++;
		for(int j = 0; j < vecinos; j++)
			dominado[vecino[j]]++;
	}
	for(int i = 0; i < nodosComponente; i++){
		int nodo = componente[i];
		es = es && (dominado[nodo] > 0);
	}
	return es;
}

//Busqueda local con cantidad de iteraciones y solucion inicial pasadas
//por parametro
vint localConInicial(
	const Grafo & grafo, 
	const vint & componente, 
	const vint & inicial,
	int iteraciones
){
	
	vint solucion = inicial;
	int nodosCompo = componente.size();
	unsigned int minimo = inicial.size(); //Minimo hasta ahora
	for(int contador = iteraciones; contador > 0; contador--){
		int  nodosSolucion = solucion.size(),
		     gradoMinimo = grafo.nodos()+1, aEliminar = -1;
		
		for(int i = 0; i < nodosSolucion; i++){
			//Probar removerlo
			int nodo = solucion[i];
			int grado = grafo.vecinos(nodo).size();
			
			int candidato = (aEliminar >= 0) ? solucion[aEliminar] : -1;
			if(dominaComponente(grafo,componente,solucion,nodo)
				&& (gradoMinimo > grado || 
					(gradoMinimo == grado && nodo > candidato))){
				//Es candidato de mejor solucion. Actualizo
				aEliminar = i;
				gradoMinimo = grado;
			}
		}
		
		if(aEliminar >= 0){
			if(minimo > solucion.size()-1){
				minimo = solucion.size()-1;
				
				swap(solucion[aEliminar],solucion[solucion.size()-1]);
				solucion.pop_back();

				contador = iteraciones+1;
			}
			continue;
		}
		int gradoMaximo = 0, indCompo = -1, indSolucion = -1;
		for(int i = 0; i < nodosCompo; i++){
			int nodoCompo = componente[i];
			if(find(solucion.begin(),solucion.end(),nodoCompo)
				!= solucion.end()){
				
				continue;
			}

			int grado = grafo.vecinos(nodoCompo).size();
			for(int j = 0; j < nodosSolucion; j++){	
				int previo = solucion[j];
				if(previo > nodoCompo) continue;
				solucion[j] = nodoCompo;

				int campeonCompo = (indCompo >= 0) ? componente[indCompo] : -1;			
				if(dominaComponente(grafo,componente,solucion)
					 && (gradoMaximo < grado || 
						(gradoMaximo == grado && nodoCompo > campeonCompo))){
					
					indCompo = i;
					indSolucion = j;
					gradoMaximo = grado;
				}

				solucion[j] = previo;
			}
		}
		
		if(indCompo == -1)
			break;
		
		solucion[indSolucion] = componente[indCompo];
	}
	return solucion;
}

static int iteraciones;
void iteracionesLocal(int iters){
	assert(iters > 0);
	iteraciones = iters;
}

//Busqueda local (Ejercicio 3)
vint local(const Grafo & grafo, const vint & componente){
	//Realiza la busqueda local desde todos los nodos.
	return localConInicial(grafo,componente,componente,iteraciones);
}
